/*
 * @lc app=leetcode.cn id=257 lang=cpp
 *
 * [257] 二叉树的所有路径
 *
 * https://leetcode-cn.com/problems/binary-tree-paths/description/
 *
 * algorithms
 * Easy (69.41%)
 * Likes:    702
 * Dislikes: 0
 * Total Accepted:    193.4K
 * Total Submissions: 278.7K
 * Testcase Example:  '[1,2,3,null,5]'
 *
 * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 * 
 * 叶子节点 是指没有子节点的节点。
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [1,2,3,null,5]
 * 输出：["1->2->5","1->3"]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [1]
 * 输出：["1"]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点的数目在范围 [1, 100] 内
 * -100 <= Node.val <= 100
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:


    // void traversal(TreeNode* cur, vector<int>& path, vector<string>& res){
        
    //     path.push_back(cur->val);

    //     //终止条件，到了叶子结点
    //     if(cur->left == NULL && cur->right == NULL) {
    //         string sPath;
    //         for(int i = 0; i < path.size() - 1; i++){
    //             sPath += to_string(path[i]);
    //             sPath += "->";
    //         }

    //         sPath += to_string(path[path.size() - 1]);

    //         res.push_back(sPath);
    //         return;
    //     }

    //     if(cur->left) {
    //         traversal(cur->left, path, res);
    //         path.pop_back();
    //     }

    //     if(cur->right) {
    //         traversal(cur->right, path, res);
    //         path.pop_back();
    //     }
    // }
    // vector<string> binaryTreePaths(TreeNode* root) {
    //     vector<int> path;
    //     vector<string> res;
    //     if (root == NULL) return{};
    //     traversal(root, path, res);
    //     return res;
    // }



    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string path;

        traversal(root, path, res);

        if(root == NULL) return res;
        return res;

    }
    void traversal(TreeNode* cur, string path, vector<string>& res) {
        path += to_string(cur->val);
        if(cur->left == NULL && cur->right == NULL){
            res.push_back(path);
            return;
        }
        if(cur->left) {
            traversal(cur->left, path + "->", res);
        }
        if(cur->right) {
            traversal(cur->right, path + "->", res);
        }

        // return;
    }



// private:

//     void traversal(TreeNode* cur, string path, vector<string>& result) {
//         path += to_string(cur->val); // 中
//         if (cur->left == NULL && cur->right == NULL) {
//             result.push_back(path);
//             return;
//         }
//         if (cur->left) traversal(cur->left, path + "->", result); // 左
//         if (cur->right) traversal(cur->right, path + "->", result); // 右
//     }

// public:
//     vector<string> binaryTreePaths(TreeNode* root) {
//         vector<string> result;
//         string path;
//         if (root == NULL) return result;
//         traversal(root, path, result);
//         return result;

//     }

};
// @lc code=end

